/* 416. 分割等和子集 */
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
	let sum = 0
	for (const num of nums) {
		sum += num
	}
	if (sum % 2 !== 0) return false
	const target = sum / 2
	const memo = new Map()
	const dfs = (curSum, i) => {
		// 越界 或者 比目标值大
		if (i === nums.length || curSum > target) return false
		if (curSum === target) return true

		/*
            选nums[i] 当前和变成 curSum + nums[i] 指针移动一位
            不选nums[i] 当前和还是curSum 指针移动一位  
        */
		const key = curSum + '&' + i //描述一个问题的key
		if (memo.has(key)) return memo.get(key)
		const res = dfs(curSum + nums[i], i + 1) || dfs(curSum, i + 1)
		memo.set(key, res)
		return res
	}
	return dfs(0, 0)
}
const ret = canPartition([1, 2, 3, 4, 5, 6, 7])
console.log('canPartition :>>', ret)
